Ranking tournaments

Abstract

Ranking is a fundamental activity for organizing and, later, understanding data. Advice of the form “ a should be ranked before b ” is given. If this advice is consistent, and complete, then there is a total ordering on the data and the ranking problem is essentially a sorting problem. If the advice is consistent, but incomplete, then the problem becomes topological sorting. If the advice is inconsistent, then we have the feedback arc set (FAS) problem: The aim is then to rank a set of items to satisfy as much of the advice as possible. An instance in which there is advice about every pair of items is known as a tournament. This ranking task is..